#include <iostream>
using std::cout;
using std::endl;

typedef int DataType;

struct Node {
  DataType data;
  Node* next;
};

void Insert(Node** head, DataType data) {
  Node* node = new Node;
  node->data = data;
  node->next = *head;
  *head = node;
}

void Print(Node* head) {
  Node* p = head;
  while (p) {
    cout << p->data << ' ';
    p = p->next;
  }
  cout << endl;
}

// 单链表反转（简单方法：链表A移除头节点、插入到链表B头部）
void Reverse(Node** head) {
  Node* p = *head;
  Node* p1 = p ? p->next : nullptr;
  Node* p2 = p1 ? p1->next : nullptr;
  while (p && p1) {
    p1->next = p;
    p = p1;
    p1 = p2;
    if (p2) p2 = p2->next;
  }
  if (*head) (*head)->next = nullptr;
  *head = p;
}
void TestReverse() {
  Node* head = nullptr;
  for (int i = 0; i < 5; ++i) {
    Insert(&head, i);
  }
  Print(head);
  Reverse(&head);
  Print(head);
}

// 检测是否有环
bool HasRing(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
  }
  return false;
}
void TestHasRing() {
  Node* head = nullptr;
  for (int i = 0; i < 5; ++i) {
    Insert(&head, i);
  }
  head->next->next->next = head->next;
  // Print(head);
  if (HasRing(head))
    cout << "HasRing\n";
  else
    cout << "NotRing\n";
}

// 两个有序链表合并
// TODO: 都Move到新链表更简单 空间复杂度也是O(1)
Node* Merge(Node* head1, Node* head2) {
  if (head1 == nullptr) return head2;
  if (head2 == nullptr) return head1;
  Node* p1 = head1;
  Node* p2 = head2;
  // 循环里用到p1和p2，所以while条件判断这些不为nullptr
  while (p1 && p2) {
    // 要修改前驱的next指向，所以需要用p->next来判断（因为单链表找不到pre节点）
    // 循环条件用到哪个指针就要先确保它不为nullptr
    while (p1->next && p1->next->data <= p2->data) {
      p1 = p1->next;
    }
    if (p1 && p1->next == nullptr) {
      p1->next = p2;
      return head1;
    }
    Node* begin = p2;
    while (p1->next && p2->next && p2->next->data <= p1->next->data) {
      p2 = p2->next;
    }
    // 可能断掉，临时保存next
    Node* p1n = p1->next;
    Node* p2n = p2->next;
    // 修改next指针
    p1->next = begin;
    p2->next = p1n;
    // 后移位置指针
    p1 = p1n;
    p2 = p2n;
  }
  return head1;
}

void TestMerge() {
  Node* head1 = nullptr;
  Insert(&head1, 8);
  Insert(&head1, 5);
  Insert(&head1, 1);
  Insert(&head1, 1);
  Insert(&head1, 0);
  Print(head1);

  Node* head2 = nullptr;
  Insert(&head2, 9);
  Insert(&head2, 8);
  Insert(&head2, 6);
  Insert(&head2, 3);
  Insert(&head2, 1);
  Insert(&head2, 1);
  Print(head2);

  Node* head = Merge(head1, head2);
  Print(head);
}

// 删除链表倒数第n个节点
bool DeleteLastN(Node** head, int n) {
  if (n <= 0) return false;
  Node* pre = *head;
  Node* tail = *head;
  int i = 0;
  while (tail) {
    tail = tail->next;
    if (i > n) {
      pre = pre->next;
    }
    ++i;
  }
  if (i < n) {
    return false;
  } else if (i == n) {
    Node* todel = *head;
    *head = (*head)->next;
    delete todel;
  } else {
    Node* todel = pre->next;
    pre->next = pre->next->next;
    delete todel;
  }
  return true;
}
void TestDeleteLastN() {
  Node* head1 = nullptr;
  Insert(&head1, 1);
  Insert(&head1, 2);
  Insert(&head1, 3);
  Insert(&head1, 4);
  Insert(&head1, 5);
  Print(head1);
  DeleteLastN(&head1, 2);
  Print(head1);
}

// 中间节点
bool MiddleData(Node* head, DataType& data) {
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  if (slow) {
    data = slow->data;
    return true;
  } else {
    return false;
  }
}
void TestMiddleData() {
  Node* head1 = nullptr;
  Insert(&head1, 1);
  Insert(&head1, 2);
  // Insert(&head1, 3);
  Insert(&head1, 4);
  Print(head1);
  int data;
  if (MiddleData(head1, data)) cout << "MiddleData:" << data << endl;
}

int main() {
  TestReverse();
  TestHasRing();
  TestMerge();
  TestDeleteLastN();
  TestMiddleData();
}